package com.huangkailong.leetcode;

/**
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i,ai) 。在坐标内画 n 条垂直线，垂直线 i的两个端点分别为(i,ai) 和 (i, 0) 。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。<br/>
 * <br/>
 * 说明：你不能倾斜容器。<br/>
 * <br/>
 * <br/>
 * <br/>
 * 示例 1：<br/>
 * <br/>
 * <br/>
 * <br/>
 * 输入：[1,8,6,2,5,4,8,3,7]<br/>
 * 输出：49 <br/>
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。<br/>
 * 示例 2：<br/>
 * <br/>
 * 输入：height = [1,1]<br/>
 * 输出：1<br/>
 * 示例 3：<br/>
 * <br/>
 * 输入：height = [4,3,2,1,4]<br/>
 * 输出：16<br/>
 * 示例 4：<br/>
 * <br/>
 * 输入：height = [1,2,1]<br/>
 * 输出：2<br/>
 * <br/>
 * <br/>
 * 提示：<br/>
 * <br/>
 * n = height.length<br/>
 * 2 <= n <= 3 * 104<br/>
 * 0 <= height[i] <= 3 * 104<br/>
 * <br/>
 * @author huangkl
 * @date 2021-05-21 16:05
 */
public class MaxArea {
    /**
     * 暴力枚举
     * leetcode 上会超时
     */
    public static int solution1(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }

        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i+1; j < height.length; j++) {
                int w = j-i;
                int h = Math.min(height[i], height[j]);
                int area = w*h;
                if(area > maxArea){
                    maxArea  = area;
                }
            }
        }

        return maxArea;
    }

    /**
     * 双指针
     */
    public static int solution2(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }

        int maxArea = 0;
        int l = 0;
        int r = height.length-1;
        while (l <= r){
            int w = r-l;
            int h = Math.min(height[l], height[r]);
            int area = w*h;
            if(area > maxArea){
                maxArea  = area;
            }
            if(height[l] <= height[r]){
                l++;
            }else{
                r--;
            }
        }

        return maxArea;
    }
}
